/// https://leetcode-cn.com/problems/container-with-most-water/
pub struct Solution;

impl Solution {
    pub fn double_pointer(height: Vec<i32>) -> i32 {
        let (mut i, mut j, mut ans, mut _temp) = (0, height.len() - 1, 0, 0);
        while i < j {
            _temp = if height[i] < height[j] {
                i += 1;
                (j - i + 1) as i32 * height[i - 1]
            } else {
                j -= 1;
                (j - i + 1) as i32 * height[j + 1]
            };
            ans = if _temp > ans { _temp } else { ans };
        }
        ans
    }

    pub fn double_pointer_vec(height: Vec<i32>) -> i32 {
        let (mut i, mut j) = (0, height.len() - 1);
        let mut v: Vec<i32> = Vec::with_capacity(j / 2 + 1);
        while i < j {
            if height[i] < height[j] {
                v.push((j - i) as i32 * height[i]);
                i += 1;
            } else {
                v.push((j - i) as i32 * height[j]);
                j -= 1;
            }
        }
        *v.iter().max().unwrap()
    }

    pub fn width_shrink(height: Vec<i32>) -> i32 {
        let len: usize = height.len();
        let mut area: Vec<i32> = Vec::with_capacity(len);
        for k in 1..height.len() {
            for l in (0..k).rev() {
                area.push((height[len - k + l]).min(height[l]) * (len - k) as i32);
                // println!("({},{})", height.len() - k + l, l);
            }
        }
        *area.iter().max().unwrap()
    }

    pub fn simple_for(height: Vec<i32>) -> i32 {
        let mut arr: Vec<i32> = Vec::with_capacity(height.len() * height.len());
        for i in 0..height.len() - 1 {
            for j in (i + 1)..height.len() {
                arr.push((j - i) as i32 * height[i].min(height[j]));
            }
        }
        *arr.iter().max().unwrap()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>) -> i32 {
        let v = vec![1, 1, 1, 2];
        assert_eq!(f(v), 3);

        let v = vec![1, 8, 6, 2, 5, 4, 8, 3, 7];
        assert_eq!(f(v), 49);

        let v = vec![1, 1,];
        assert_eq!(f(v), 1);

        let v = vec![4, 3, 2, 1, 4];
        assert_eq!(f(v), 16);

        let v = vec![1, 2, 1];
        assert_eq!(f(v), 2);
    }

    bench!(assert Solution::simple_for);
    bench!(assert Solution::width_shrink);
    bench!(assert Solution::double_pointer);
    bench!(assert Solution::double_pointer_vec);
}
